package com.lw.leetcode.back.b;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * create by idea
 * 365. 水壶问题
 *
 * @author lmx
 * @version 1.0
 * @date 2021/12/30 17:13
 */
public class CanMeasureWater {


    public static void main(String[] args) {
        CanMeasureWater test = new CanMeasureWater();

        // ture
//        int a = 3;
//        int b = 5;
//        int c = 4;

        // false
//        int a = 2;
//        int b = 6;
//        int c = 5;

        // true
        int a = 104579;
        int b = 104593;
        int c = 12444;

        boolean b1 = test.canMeasureWater(a, b, c);
        System.out.println(b1);
    }


    public boolean canMeasureWater(int a, int b, int c) {
        if (a + b < c) {
            return false;
        }
        if (a + b == c) {
            return true;
        }
        Set<Long> set = new HashSet<>();
        LinkedList<Long> list = new LinkedList<>();
        long item = 0L;
        list.add(item);
        while (!list.isEmpty()) {
            long p = list.pop();
            if (set.contains(p)) {
                continue;
            }
            set.add(p);
            int x = (int) (p >> 32);
            int y = (int) p;
            if (x == c || y == c || x + y == c) {
                return true;
            }
            list.add((long) y);
            list.add(((long) x) << 32);
            list.add((((long) a) << 32) | y);
            list.add((((long) x) << 32) | b);
            long t = Math.min(x, b - y);
            list.add((((long) x - t) << 32) | (y + t));
            t = Math.min(a - x, y);
            list.add((((long) x + t) << 32) | (y - t));
        }
        return false;
    }


}
